{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "collapsed": true
   },
   "source": [
    "# String Permutation\n",
    "\n",
    "## Problem Statement\n",
    "\n",
    "Given a string, write a function that uses recursion to output a list of all the possible permutations of that string.\n",
    "\n",
    "For example, given s='abc' the function should return ['abc', 'acb', 'bac', 'bca', 'cab', 'cba']\n",
    "\n",
    "*Note: If a character is repeated, treat each occurence as distinct, for example an input of 'xxx' would return a list with 6 \"versions\" of 'xxx'*\n",
    "\n",
    "\n",
    "## Fill Out Your Solution Below\n",
    "\n",
    "Let's think about what the steps we need to take here are:\n",
    "\n",
    "1. Iterate through the initial string – e.g., ‘abc’.\n",
    "\n",
    "* For each character in the initial string, set aside that character and get a list of all permutations of the string that’s left. So, for example, if the current iteration is on 'b', we’d want to find all the permutations of the string 'ac'.\n",
    "\n",
    "* Once you have the list from step 2, add each element from that list to the character from the initial string, and append the result to our list of final results. So if we’re on 'b' and we’ve gotten the list ['ac', 'ca'], we’d add 'b' to those, resulting in 'bac' and 'bca', each of which we’d add to our final results.\n",
    "\n",
    "* Return the list of final results.\n",
    "\n",
    "Let's go ahead and see this implemented:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "def permute(s):\n",
    "    out = []\n",
    "    \n",
    "    # Base Case\n",
    "    if len(s) == 1:\n",
    "        out = [s]\n",
    "        \n",
    "    else:\n",
    "        # For every letter in string\n",
    "        for i, let in enumerate(s):\n",
    "            \n",
    "            # For every permutation resulting from Step 2 and 3 described above\n",
    "            for perm in permute(s[:i] + s[i+1:]):\n",
    "                \n",
    "                # Add it to output\n",
    "                out += [let + perm]\n",
    "\n",
    "    return out"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['abc', 'acb', 'bac', 'bca', 'cab', 'cba']"
      ]
     },
     "execution_count": 24,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "permute('abc')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "____\n",
    "# Test Your Solution"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "All test cases passed.\n"
     ]
    }
   ],
   "source": [
    "\"\"\"\n",
    "RUN THIS CELL TO TEST YOUR SOLUTION.\n",
    "\"\"\"\n",
    "\n",
    "from nose.tools import assert_equal\n",
    "\n",
    "class TestPerm(object):\n",
    "    \n",
    "    def test(self,solution):\n",
    "        \n",
    "        assert_equal(sorted(solution('abc')),sorted(['abc', 'acb', 'bac', 'bca', 'cab', 'cba']))\n",
    "        assert_equal(sorted(solution('dog')),sorted(['dog', 'dgo', 'odg', 'ogd', 'gdo', 'god']) )\n",
    "        \n",
    "        print 'All test cases passed.'\n",
    "        \n",
    "\n",
    "\n",
    "# Run Tests\n",
    "t = TestPerm()\n",
    "t.test(permute)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "___\n",
    "# Conclusion\n",
    "\n",
    "There were two main takeaways from tackling this problem:\n",
    "\n",
    "* Every time we put a new letter in position i, we then had to find all the possible combinations at position i+1 – this was the recursive call that we made. How do we know when to save a string? When we are at a position i that is greater than the number of letters in the input string, then we know that we have found one valid permutation of the string and then we can add it to the list and return to changing letters at positions less than i. This was our base case – remember that we always must have a recursive case and a base case when using recursion!\n",
    "\n",
    "\n",
    "* Another big part of this problem was figuring out which letters we can put in a given position. Using our sample string “abc”, lets say that we are going through all the permutations where the first letter  is \"c”. Then, it should be clear that the letter in the 2nd and 3rd position can only be either “a” or “b”, because “a” is already used. As part of our algorithm, we have to know which letters can be used in a given position – because we can’t reuse the letters that were used in the earlier positions. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Good Job!"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.2"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
